package 力扣题库;

public class p108将有序数组转换为二叉搜索树 {
    public TreeNode sortedArrayToBST(int[] nums) {
        //注意：题目要求BST要高度平衡
        //只知道中序遍历的结果，不能唯一确定一棵树。增加条件 BST高度平衡，仍然不能唯一确定一棵树
        //观察可能的树，发现我们选择数组中间的数作为根节点，分给左右子树的节点个数相同，或只相差1，保证树的平衡
        // 数组长度是奇数，则根节点的选择是唯一的
        // 数组长度是偶数，可以选择 中间位置左边的数字作为根节点 或者 选择中间位置右边的数字作为根节点，选择不同数字作根节点创建的平衡二叉搜索树是不同的
        return helper(nums,0,nums.length-1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        if (left>right) {
            return null;
        }
        int mid=(left+right)/2; //选择 中间位置左边的数字作为根节点
        TreeNode root=new TreeNode(nums[mid]);
        root.left=helper(nums,left,mid-1);
        root.right=helper(nums,mid+1,right);

        return root;
    }
}
